#include<iostream>
#include<string>
#include<vector>
using namespace std;

//这里重新实现堆排序
//生成大顶堆
vector<int> arr={3,2,1,4,5,6,11,7,90,66};

void swap(int *a,int *b){
    int temp=(*a);
    (*a)=*b;
    (*b)=temp;
}
void show(vector<int> arr){
        int size=arr.size();
        for(int i=0;i<size;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}
/// @brief 不断的交换节点
/// @param arr 无序数组
/// @param start 开始节点
/// @param end 结束节点
void sift_down(vector<int> &arr,int start,int end){
    //先找较小的孩子
    int parent=start;//当前父节点，因为后面会改变这个指针，所以要保存
    int child=parent*2+1;//左孩子
    while(child<=end){
        //先比较两个子节点的大小，并把child置为较大的哪一个的下标
        if(child+1<=end&&arr[child]<arr[child+1]){
            child++;
        }
        if(arr[parent]>=arr[child]){//parent本身就大
            return;
        }else{
            //交换并移动父节点指针
            swap(&arr[parent],&arr[child]);
            parent=child;
            child=parent*2+1;
        }
    }
}

//初始数组
void heapSort(vector<int> &arr){
    //获取最后一个元素的下标
    int last_node=arr.size()-1;
    //堆排序要从最后一个元素的父节点开始网上递归查找
    int parent_node=(last_node-1)/2;
    //对这些父节点迭代，从下往上，从右往左
    for(int i=(last_node-1)/2;i>=0;i--){
        sift_down(arr,i,arr.size()-1);
        
        printf("当前父节点选择 %d : ",i);
        show(arr);
    }
}

int main(void){

    heapSort(arr);
    printf("排序完成 \n");
    show(arr);
    return 0;
}